3468. A Simple Problem with Integers

You have n integers, a₁, a₂, ... , a_n. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input. The first line contains two numbers n and q (1 ≤ n, q ≤ 100000).

The second line contains n numbers, the initial values of a₁, a₂, ... , a_n (-10⁹ ≤ a_i ≤ 10⁹).

Each of the next q lines represents an operation:

“C a b c” means adding c to each of a_a, a_a+1, ... , a_b (-10000 ≤ c ≤ 10000).

“Q a b” means querying the sum of a_a, a_a+1, ... , a_b.

Output. You need to answer all q commands in order. One answer in a line.

Sample input

10 5

1 2 3 4 5 6 7 8 9 10

Q 4 4

Q 1 10

Q 2 4

C 3 6 3

Q 2 4

Sample output

4

55

9

15

РЕШЕНИЕ

структуры данных – дерево отрезков

Анализ алгоритма

Реализуем дерево отрезков, поддерживающее:

· суммирование на отрезке

· прибавление числа ко всем элементам на отрезке

Реализация алгоритма

#include <cstdio>

#include <algorithm>

#include <cstring>

#define MAX 100010

using namespace std;

struct node

{

long long summa, add;

} t[4*MAX];

void build(int *mas, int v, int Left, int Right)

{

if (Left == Right)

t[v].summa = mas[Left], t[v].add = 0;

else

{

int Middle = (Left + Right) / 2;

build (mas, v*2, Left, Middle);

build (mas, v*2+1, Middle+1, Right);

t[v].summa = t[v*2].summa + t[v*2+1].summa;

t[v].add = 0;

}

}

void Push(int v, int LeftPos, int Middle, int RightPos)

{

if (t[v].add)

{

t[2*v].add += t[v].add;

t[2*v].summa += (Middle - LeftPos + 1) * t[v].add;

t[2*v+1].add += t[v].add;

t[2*v+1].summa += (RightPos - Middle) * t[v].add;

t[v].add = 0;

}

}

void AddValue(int v, int LeftPos, int RightPos, int L, int R, int Value)

{

if (L > R) return;

if ((LeftPos == L) && (RightPos == R))

{

t[v].add += Value;

t[v].summa += (R - L + 1) * Value;

return;

}

int Middle = (LeftPos + RightPos) / 2;

Push(v,LeftPos,Middle,RightPos);

AddValue(2*v, LeftPos, Middle, L, min(Middle,R), Value);

AddValue(2*v+1, Middle+1, RightPos, max(L,Middle+1), R, Value);

t[v].summa = t[2*v].summa + t[2*v+1].summa;

}

long long Summa(int v, int LeftPos, int RightPos, int L, int R)

{

if (L > R) return 0;

if ((LeftPos == L) && (RightPos == R)) return t[v].summa;

int Middle = (LeftPos + RightPos) / 2;

Push(v,LeftPos,Middle,RightPos);

return Summa(2*v, LeftPos, Middle, L, min(Middle,R)) +

Summa(2*v+1, Middle+1, RightPos, max(L,Middle+1), R);

}

int i, n, q, tests;

int a, b, c;

char command;

int mas[MAX];

int main(void)

{

scanf("%d %d",&n,&q);

for(i = 1; i <= n; i++)

scanf("%d",&mas[i]);

build(mas, 1, 1, n) ;

scanf("\n");

for(i = 0; i < q; i++)

{

scanf("%c ",&command);

if (command == 'C')

{

scanf("%d %d %d\n",&a,&b,&c);

AddValue(1,1,n,a,b,c);

}

else

{

scanf("%d %d\n",&a,&b);

printf("%lld\n",Summa(1,1,n,a,b));

}

}

return 0;

}